{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count the Number of Complete Components"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countCompleteComponents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计完全连通分量的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code> 。现有一个包含 <code>n</code> 个顶点的 <strong>无向</strong> 图，顶点按从 <code>0</code> 到 <code>n - 1</code> 编号。给你一个二维整数数组 <code>edges</code> 其中 <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> 表示顶点 <code>a<sub>i</sub></code> 和 <code>b<sub>i</sub></code> 之间存在一条 <strong>无向</strong> 边。</p>\n",
    "\n",
    "<p>返回图中 <strong>完全连通分量</strong> 的数量。</p>\n",
    "\n",
    "<p>如果在子图中任意两个顶点之间都存在路径，并且子图中没有任何一个顶点与子图外部的顶点共享边，则称其为 <strong>连通分量</strong> 。</p>\n",
    "\n",
    "<p>如果连通分量中每对节点之间都存在一条边，则称其为 <strong>完全连通分量</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/04/11/screenshot-from-2023-04-11-23-31-23.png\" style=\"width: 671px; height: 270px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>如上图所示，可以看到此图所有分量都是完全连通分量。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/04/11/screenshot-from-2023-04-11-23-32-00.png\" style=\"width: 671px; height: 270px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>包含节点 0、1 和 2 的分量是完全连通分量，因为每对节点之间都存在一条边。\n",
    "包含节点 3 、4 和 5 的分量不是完全连通分量，因为节点 4 和 5 之间不存在边。\n",
    "因此，在图中完全连接分量的数量是 1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 50</code></li>\n",
    "\t<li><code>0 &lt;= edges.length &lt;= n * (n - 1) / 2</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li>不存在重复的边</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-the-number-of-complete-components](https://leetcode.cn/problems/count-the-number-of-complete-components/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-the-number-of-complete-components](https://leetcode.cn/problems/count-the-number-of-complete-components/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6\\n[[0,1],[0,2],[1,2],[3,4]]', '6\\n[[0,1],[0,2],[1,2],[3,4],[3,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        adjList = [[] for _ in range(n)]\n",
    "        for from_, to in edges:\n",
    "            adjList[from_].append(to)\n",
    "            adjList[to].append(from_)\n",
    "        \n",
    "        visited = [0] * n\n",
    "        def dfs(node, edge_count):\n",
    "            visited[node] = 1\n",
    "            count = 1\n",
    "            ans = True\n",
    "            if len(adjList[node]) != edge_count:\n",
    "                ans = False\n",
    "\n",
    "            for neighbor in adjList[node]:\n",
    "                if visited[neighbor] == 0:\n",
    "                    temp, c = dfs(neighbor, edge_count)\n",
    "                    count += c\n",
    "                    ans &= temp\n",
    "            return ans, count\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            if visited[i] == 0:\n",
    "                c, t = dfs(i, len(adjList[i]))\n",
    "                if t == len(adjList[i]) + 1:\n",
    "                    count += c\n",
    "        return count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [1 << i for i in range(n)]\n",
    "        for i, j in edges:\n",
    "            g[i] |= 1 << j\n",
    "            g[j] |= 1 << i\n",
    "        d = defaultdict(int)\n",
    "        for i, x in enumerate(g):\n",
    "            d[x] |= 1 << i\n",
    "        return sum(k == v for k, v in d.items())\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        UFS, degree = list(range(n)), [0 for _ in range(n)]\n",
    "        for x in edges:\n",
    "            degree[x[0]] += 1\n",
    "            degree[x[1]] += 1\n",
    "            stack1, stack2 = [x[0]], [x[1]]\n",
    "            while UFS[stack1[-1]] != stack1[-1]:\n",
    "                stack1.append(UFS[stack1[-1]])\n",
    "            while UFS[stack2[-1]] != stack2[-1]:\n",
    "                stack2.append(UFS[stack2[-1]])\n",
    "            root = stack1.pop()\n",
    "            while stack1:\n",
    "                UFS[stack1.pop()] = root\n",
    "            while stack2:\n",
    "                UFS[stack2.pop()] = root\n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            stack = [i]\n",
    "            while UFS[stack[-1]] != stack[-1]:\n",
    "                stack.append(UFS[stack[-1]])\n",
    "            for x in stack:\n",
    "                dic.setdefault(stack[-1], set()).add(x)\n",
    "        return sum(all(degree[y] == len(dic[x]) - 1 for y in dic[x]) for x in dic)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        if not edges:\n",
    "            return n\n",
    "\n",
    "        idx = list(range(n))\n",
    "        def find_idx(x):\n",
    "            if idx[x] != x:\n",
    "                idx[x] = find_idx(idx[x])\n",
    "            return idx[x]\n",
    "\n",
    " \n",
    "        ans = defaultdict(int)\n",
    "        for a, b in edges:\n",
    "            a_x = find_idx(a)\n",
    "            b_x = find_idx(b)\n",
    "            if a_x != b_x:\n",
    "                if a_x > b_x:\n",
    "                    idx[a_x] = b_x\n",
    "                else:\n",
    "                    idx[b_x] = a_x\n",
    "        for a, b in edges:\n",
    "            a_x = find_idx(a)\n",
    "            b_x = find_idx(b)\n",
    "            if a_x == b_x:\n",
    "                ans[a_x] += 1\n",
    " \n",
    "        res = Counter(idx)\n",
    "        result = 0\n",
    "        for key, value in res.items():\n",
    "            if value*(value-1)/2 == ans[key] :\n",
    "                result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        p = list(range(n))\n",
    "        cnt = [0] * n\n",
    "        \n",
    "        def find(x):\n",
    "            while x != p[x]: p[x] = x = p[p[x]]\n",
    "            return x\n",
    "        \n",
    "        for e in edges:\n",
    "            a, b = map(find, e)\n",
    "            if a != b:\n",
    "                p[a] = b\n",
    "                cnt[b] += cnt[a]\n",
    "            cnt[b] += 1\n",
    "\n",
    "        return sum(cnt[x] == v * (v - 1) // 2 for x, v in Counter(map(find, p)).items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        d = [0] * n\n",
    "        g = [[] for _ in range(n)]\n",
    "        vis = [False] * n\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "            d[x] += 1\n",
    "            d[y] += 1\n",
    "        \n",
    "\n",
    "        def dfs(x):\n",
    "            t = 1\n",
    "            e = d[x]\n",
    "            vis[x] = True\n",
    "            for y in g[x]:\n",
    "                if not vis[y]:\n",
    "                    tt, ee = dfs(y)\n",
    "                    t += tt\n",
    "                    e += ee\n",
    "            return t, e\n",
    "\n",
    "        \n",
    "        \n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                m, e = dfs(i)\n",
    "                if m * (m - 1) == e:\n",
    "                    res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        vis = [False] * n\n",
    "        def dfs(x: int) -> None:\n",
    "            vis[x] = True\n",
    "            nonlocal e, v\n",
    "            v += 1\n",
    "            e += len(g[x]) \n",
    "            for y in g[x]:\n",
    "                if not vis[y]:\n",
    "                    dfs(y)\n",
    "        ans = 0\n",
    "        for i, b in enumerate(vis):\n",
    "            if not b: \n",
    "                v = e = 0\n",
    "                dfs(i)\n",
    "                ans += e == v * (v - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        UF = UnionFind(n)\n",
    "        for u, v in edges:\n",
    "            UF.unionSet(u, v) \n",
    "\n",
    "        roots = set(UF.findSet(i) for i in range(n))\n",
    "\n",
    "        ans = sum(UF.edgeCount[v] == comb(UF.sizeSets[v], 2)for v in roots)\n",
    "\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int, m: int=None) -> None:\n",
    "        \"\"\"\n",
    "        build m disjoint sets from n nodes\n",
    "        T: O(N)\n",
    "        \"\"\"\n",
    "        self.parents = list(range(n))    # parrent array: parent node of each node\n",
    "        self.ranks = [0] * n            # rank array: max height of each node\n",
    "        self.sizeSets = [1] * n         # size of each disjoint set\n",
    "        self.numSets = n                # number of disjoint sets\n",
    "        self.edgeCount = [0] * n        # number of edges in each disjoint set\n",
    "\n",
    "        # 当m不等于n时，随机选2个互斥集合合并，直到有m个互斥集合\n",
    "        if m:\n",
    "            k = n-m\n",
    "            while k:\n",
    "                # 随机选2个互斥集合合并\n",
    "                i, j = random.sample(self.parents, 2)\n",
    "                while self.isSameSet(i, j):\n",
    "                    i, j = random.sample(self.parents, 2)\n",
    "                self.unionSet(i, j)\n",
    "                k -= 1\n",
    "    \n",
    "\n",
    "    def findSet(self, i: int) -> int:\n",
    "        \"\"\"return root of node i's set\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "           path-compression: keep the trees very flat\n",
    "           Iteration\n",
    "        \"\"\"\n",
    "        root = i  # parent of i \n",
    "        children = []   # 记录从当前节点到根节点路径上的所有节点\n",
    "\n",
    "        # 从当前节点开始，向上查找父节点\n",
    "        while root != self.parents[root]:\n",
    "            children.append(root)\n",
    "            root = self.parents[root]\n",
    "\n",
    "        # 路径压缩：一条路径上的所有节点都变成叶节点，直接连接根节点\n",
    "        # 路径压缩后，树会变矮，但不更新这些节点的rank值，继续用于union()\n",
    "        for c in children:\n",
    "            self.parents[c] = root\n",
    "        \n",
    "        # 返回根节点\n",
    "        return root\n",
    "    \n",
    "    def unionSet(self, i: int, j: int) -> None:\n",
    "        \"\"\"若节点i和节点j来自2个不同的互斥集合，将两个集合合并 \n",
    "           union by rank   矮树作为高树的子树\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        ip, jp = self.findSet(i), self.findSet(j)\n",
    "\n",
    "        # 若两个节点来自同一互斥集合，返回\n",
    "        if ip == jp:\n",
    "            self.edgeCount[ip] += 1\n",
    "            return \n",
    "\n",
    "        # 若A树矮，B树高，A树连到B树的根节点上，新树rank不变\n",
    "        if self.ranks[ip] < self.ranks[jp]:\n",
    "            self.parents[ip] = jp\n",
    "            self.sizeSets[jp] += self.sizeSets[ip]\n",
    "            self.edgeCount[jp] += self.edgeCount[ip] + 1\n",
    "\n",
    "        # 若B树矮，A树高，B树连到A树的根节点上，新树rank不变\n",
    "        elif self.ranks[jp] < self.ranks[ip]:\n",
    "            self.parents[jp] = ip\n",
    "            self.sizeSets[ip] += self.sizeSets[jp]\n",
    "            self.edgeCount[ip] += self.edgeCount[jp] + 1\n",
    "\n",
    "        # 若两树等高，任选一种方案，新树 rank +1\n",
    "        else:\n",
    "            self.parents[jp] = ip\n",
    "            self.sizeSets[ip] += self.sizeSets[jp]\n",
    "            self.edgeCount[ip] += self.edgeCount[jp] + 1\n",
    "            self.ranks[ip] += 1\n",
    "\n",
    "        # 互斥集总数-1\n",
    "        self.numSets -= 1\n",
    "    \n",
    "    def isSameSet(self, i: int, j: int) -> bool:\n",
    "        \"\"\"判断节点i和节点j是否属于同一集合\n",
    "           T: O(α(N) first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        # path compression twice\n",
    "        return self.findSet(i) == self.findSet(j)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [1 << i for i in range(n)]\n",
    "        for i, j in edges:  # map node to (component if fully connected else edges)\n",
    "            g[i] |= 1 << j\n",
    "            g[j] |= 1 << i\n",
    "        d = defaultdict(int)  # map component to node collections\n",
    "        for i, x in enumerate(g):\n",
    "            d[x] |= 1 << i\n",
    "        return sum(k == v for k, v in d.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        p = list(range(n))\n",
    "        cnt = [0] * n\n",
    "        \n",
    "        def find(x):\n",
    "            while x != p[x]:\n",
    "                p[x] = x = p[p[x]]\n",
    "            return x\n",
    "        \n",
    "        for e in edges:\n",
    "            a, b = map(find, e)\n",
    "            p[find(a)] = find(b)\n",
    "            if a != b:\n",
    "                cnt[b] += cnt[a]\n",
    "            cnt[b] += 1\n",
    "\n",
    "        return sum(cnt[x] == v * (v - 1) // 2 for x, v in Counter(map(find, p)).items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # for a completed comnents with node m, its edge count will be e = m(m-1)/2\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        res = 0\n",
    "        visited = [False] * n \n",
    "        for i, isVisited in enumerate(visited):\n",
    "            if isVisited == False:\n",
    "                # count node, edges \n",
    "                m, e = 0, 0\n",
    "                q = deque([i])\n",
    "                visited[i] = True\n",
    "                while q:\n",
    "                    u = q.popleft()\n",
    "                    m += 1\n",
    "                    e += len(g[u])\n",
    "                    for v in g[u]:\n",
    "                        if visited[v] == False:\n",
    "                            q.append(v)\n",
    "                            visited[v] = True \n",
    "                if e == m * (m -1):\n",
    "                    res += 1\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        vis = [False] * n\n",
    "        def dfs(x: int) -> None:\n",
    "            vis[x] = True\n",
    "            nonlocal v, e\n",
    "            v += 1\n",
    "            e += len(g[x]) \n",
    "            for y in g[x]:\n",
    "                if not vis[y]:\n",
    "                    dfs(y)\n",
    "        ans = 0\n",
    "        for i, b in enumerate(vis):\n",
    "            if not b: \n",
    "                v = e = 0\n",
    "                dfs(i)\n",
    "                ans += e == v * (v - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.parent = [v for v in range(n)]\n",
    "        self.edgesCnt = [0] * n\n",
    "        self.nodeCnt = [1] * n\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def union(self, x, y):\n",
    "        l, r = self.find(x), self.find(y)\n",
    "        if l == r:\n",
    "            self.edgesCnt[l] += 1\n",
    "        else:\n",
    "            self.parent[l] = r\n",
    "            self.nodeCnt[r] += self.nodeCnt[l]\n",
    "            self.edgesCnt[r] += (self.edgesCnt[l]+1)\n",
    "            self.nodeCnt[l] = 0 \n",
    "        \n",
    "    def count(self):\n",
    "        ans = 0\n",
    "        #print(self.nodeCnt)\n",
    "        #print(self.edgesCnt)\n",
    "        for i in range(self.n):\n",
    "            if self.nodeCnt[i] == 0:\n",
    "                continue\n",
    "            nodeCnt, edgesCnt = self.nodeCnt[i], self.edgesCnt[i]\n",
    "            if nodeCnt * (nodeCnt-1)//2 == edgesCnt:\n",
    "                ans +=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UF(n)\n",
    "        for l,r in edges:\n",
    "            uf.union(l, r)\n",
    "        return uf.count()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [1 << i for i in range(n)]\n",
    "        for i, j in edges:\n",
    "            g[i] |= 1 << j\n",
    "            g[j] |= 1 << i\n",
    "        d = defaultdict(int)\n",
    "        for i, x in enumerate(g):\n",
    "            d[x] |= 1 << i\n",
    "        return sum(k == v for k, v in d.items())\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        vis = [False] * n\n",
    "        def dfs(x:int) -> None:\n",
    "            vis[x] = True\n",
    "            nonlocal v, e\n",
    "            v += 1\n",
    "            e += len(g[x])\n",
    "            for y in g[x]:\n",
    "                if not vis[y]:\n",
    "                    dfs(y)\n",
    "        \n",
    "        ans = 0\n",
    "        for i, b in enumerate(vis):\n",
    "            if not b:\n",
    "                v = e = 0\n",
    "                dfs(i)\n",
    "                ans += e == v * (v - 1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        my_mat=[i for i in range(n)]\n",
    "        def find(x):\n",
    "            if my_mat[x]!=x:\n",
    "                my_mat[x]=find(my_mat[x])\n",
    "            return my_mat[x]\n",
    "\n",
    "        def union(x,y):\n",
    "            my_mat[find(x)]=find(y)\n",
    "\n",
    "        for ai,bi in edges:\n",
    "            union(ai,bi)\n",
    "\n",
    "        for i in range(n):\n",
    "            find(i)\n",
    "\n",
    "        my_dict=collections.defaultdict(int)\n",
    "        my_dict2=collections.defaultdict(int)\n",
    "\n",
    "        for ai,bi in edges:\n",
    "            my_dict[find(ai)]+=1\n",
    "\n",
    "        for i in my_mat:\n",
    "            my_dict2[i]+=1\n",
    "\n",
    "        result=0\n",
    "        for key in my_dict2.keys():\n",
    "            v1=my_dict2[key]\n",
    "            v2=v1*(v1-1)//2\n",
    "            v3=my_dict[key]\n",
    "            if v2==v3:\n",
    "                result+=1\n",
    "\n",
    "        return result\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        visited = [0]*n\n",
    "        ans = 0\n",
    "        def bfs(x):\n",
    "            v = e = 0\n",
    "            queue = collections.deque()\n",
    "            queue.append(x)\n",
    "            while queue:\n",
    "                # print(queue)\n",
    "                cur = queue.popleft()\n",
    "                if visited[cur]:\n",
    "                    continue\n",
    "                v += 1\n",
    "                e += len(g[cur])\n",
    "                visited[cur] = 1\n",
    "                for y in g[cur]:\n",
    "                    if not visited[y]: #y有可能重复加入\n",
    "                        queue.append(y)\n",
    "            return v,e\n",
    "        #在完全图中，任意两点之间都有边，相当于从 v点中选 2 个点的方案数,边数 = v*(v-1)\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                v,e = bfs(i)\n",
    "                # print(v,e)\n",
    "                if v*(v-1) == e:\n",
    "                    ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # parent = list(range(n))\n",
    "        # def find(x):\n",
    "        #     if parent[x] != x:\n",
    "        #         parent[x] = find(parent[x])\n",
    "        #     return parent[x]\n",
    "        # for i,j in edges:\n",
    "        #     a,b = find(i),find(j)\n",
    "        #     if a != b:\n",
    "        #         parent[a] = b\n",
    "        # cnt = 0\n",
    "        # for i in range(n):\n",
    "        #     if parent[i] == i:\n",
    "        #         cnt += 1\n",
    "        # print(parent)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        graph = defaultdict(list)\n",
    "        for e in edges:\n",
    "            n1,n2 = e\n",
    "            graph[n1].append(n2)\n",
    "            graph[n2].append(n1)\n",
    "        flags = [False for _ in range(n)]\n",
    "        def dfs(i):\n",
    "            cc = []\n",
    "            s = [i]\n",
    "            while len(s) > 0:\n",
    "                node = s.pop()\n",
    "                flags[node] = True\n",
    "                cc.append(node)\n",
    "                for nxt in graph[node]:\n",
    "                    if flags[nxt]:\n",
    "                        continue\n",
    "                    s.append(nxt)\n",
    "            return cc\n",
    "        def check_full_cc(cc):\n",
    "            for i in cc:\n",
    "                for j in cc:\n",
    "                    if j==i:\n",
    "                        continue\n",
    "                    if not j in graph[i]:\n",
    "                        \n",
    "                        return False\n",
    "            return True\n",
    "                    \n",
    "        nums = 0\n",
    "        for node in range(n):\n",
    "            if flags[node]:\n",
    "                continue\n",
    "            cc = dfs(node)\n",
    "            if check_full_cc(cc):\n",
    "                nums += 1\n",
    "        return nums\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        def bfs(node):\n",
    "            c = []\n",
    "            queue = collections.deque([node])\n",
    "            while queue:\n",
    "                cur = queue.popleft()\n",
    "                c.append(cur)\n",
    "                for nbr in graph[cur]:\n",
    "                    if nbr not in visited:\n",
    "                        visited.add(nbr)\n",
    "                        queue.append(nbr)\n",
    "            return c\n",
    "        \n",
    "        def judge(component):\n",
    "            # judge whether a component is complete or not \n",
    "            n = len(component)\n",
    "            for i in range(n):\n",
    "                for j in range(i+1, n):\n",
    "                    if component[j] not in graph[component[i]]:\n",
    "                        return False\n",
    "                \n",
    "            return True\n",
    "\n",
    "        # construct the graph from edges \n",
    "        graph = collections.defaultdict(list)\n",
    "        for e in edges:\n",
    "            graph[e[0]].append(e[1])\n",
    "            graph[e[1]].append(e[0])\n",
    "\n",
    "        visited = set()\n",
    "        res = 0 \n",
    "        for node in range(n):\n",
    "            if node not in visited:\n",
    "                visited.add(node)\n",
    "                component = bfs(node)\n",
    "                if judge(component):\n",
    "                    res+=1 \n",
    "\n",
    "        return res  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        uf = UnionFind(n) # 初始化size为n的并查集 并建图\n",
    "        for edge in edges:\n",
    "            uf.merge(edge[0], edge[1])\n",
    "\n",
    "        res = 0\n",
    "        # 遍历所有的component 的root\n",
    "        for x in range(n):\n",
    "            if uf.find(x) == x: # x是根节点\n",
    "                m = uf.size[x] # 他代表的component的边数\n",
    "                if m * (m-1) >> 1 == uf.edge[x]: \n",
    "                    res += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1]*n\n",
    "        self.edge = [0]*n \n",
    "        # 相较于模版新增了一个edge，记录每个点代表的component的edge数量，只有merge操作会新增一条边\n",
    "    def find(self, x) -> int:\n",
    "        parent = self.parent\n",
    "        if parent[x] == x:\n",
    "            return x\n",
    "        parent[x] = self.find(parent[x]) #路径压缩\n",
    "        return parent[x]\n",
    "    def merge(self, x, y):\n",
    "        # \n",
    "        size, parent, edge = self.size, self.parent, self.edge\n",
    "        x, y = self.find(x), self.find(y) # 将x,y映射到其root\n",
    "        if x == y:\n",
    "            edge[x] += 1 # 该root代表的component新增一条边\n",
    "            return 0\n",
    "        else:\n",
    "            if size[x] < size[y]:\n",
    "                parent[x] = y\n",
    "                size[y] += size[x]\n",
    "                edge[y] += (edge[x] + 1) \n",
    "                # 合并时y代表的componet新增了x component的边和本次merge加入的新边\n",
    "            else:\n",
    "                parent[y] = x \n",
    "                size[x] += size[y]\n",
    "                edge[x] += (edge[y] + 1)\n",
    "            return 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = {i: [] for i in range(n)}\n",
    "        for edge in edges:\n",
    "            u, v = edge\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "\n",
    "        def dfs(graph, start, visited):\n",
    "            visited.add(start)\n",
    "            vertex_count = 1\n",
    "            edge_count = 0\n",
    "            for neighbor in graph[start]:\n",
    "                if neighbor not in visited:\n",
    "                    v_count, e_count = dfs(graph, neighbor, visited)\n",
    "                    vertex_count += v_count\n",
    "                    edge_count += e_count\n",
    "            edge_count += len(graph[start])\n",
    "            return vertex_count, edge_count\n",
    "        \n",
    "        def count_connected(graph):\n",
    "            visited = set()\n",
    "            components = []\n",
    "            for node in graph:\n",
    "                if node not in visited:\n",
    "                    v_count, e_count = dfs(graph, node, visited)\n",
    "                    components.append((v_count, e_count // 2))\n",
    "            return components\n",
    "        components = count_connected(graph)\n",
    "        res = 0\n",
    "        for component in components:\n",
    "            v_count = component[0]\n",
    "            e_count = component[1]\n",
    "            if v_count * (v_count - 1) // 2 == e_count:\n",
    "                res += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 一个连通块中，任意两个点之间都有一条边，所以一个连通块中e = v * (v - 1)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        vis = [False] * n\n",
    "\n",
    "        def dfs(x):\n",
    "            vis[x] = True\n",
    "            nonlocal v, e\n",
    "            v += 1\n",
    "            e += len(g[x])\n",
    "            for y in g[x]:\n",
    "                if vis[y] == False:\n",
    "                    dfs(y)\n",
    "        ans = 0\n",
    "        for i, b in enumerate(vis):\n",
    "            if not b:\n",
    "                v = e = 0\n",
    "                dfs(i)\n",
    "                ans += e == v * (v - 1)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        edges = set(map(tuple, edges))\n",
    "        vis = [0] * n\n",
    "        ans = 0\n",
    "        for node in range(n):\n",
    "            if not vis[node]:\n",
    "                vis[node] = 1\n",
    "                q = [node]\n",
    "                flag = True\n",
    "                q = deque([node])\n",
    "                s = [node]\n",
    "                while q:\n",
    "                    tmp = q.popleft()\n",
    "                    for i in range(n):\n",
    "                        if ((i, tmp) in edges or (tmp, i) in edges) and not vis[i]:\n",
    "                            s.append(i)\n",
    "                            q.append(i)\n",
    "                            vis[i] = 1\n",
    "                for i in range(len(s)):\n",
    "                    for j in range(i + 1, len(s)):\n",
    "                        if not ((s[i], s[j]) in edges or (s[j], s[i]) in edges):\n",
    "                            flag = False\n",
    "                if flag:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        neb = [[] for _ in range(n)]\n",
    "        deg = [0] * n\n",
    "        for u, v in edges:\n",
    "            neb[u].append(v)\n",
    "            neb[v].append(u)\n",
    "            deg[u] += 1\n",
    "            deg[v] += 1\n",
    "        \n",
    "        visited = [False] * n\n",
    "\n",
    "        def dfs(u):\n",
    "            if visited[u]:\n",
    "                return 0, 0\n",
    "            visited[u] = True\n",
    "            print(f'visit {u=}')\n",
    "            res, res2 = 1, deg[u]\n",
    "            for v in neb[u]:\n",
    "                cnt, vdeg = dfs(v)\n",
    "                res += cnt\n",
    "                res2 += vdeg\n",
    "            return res, res2\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                cnt, vdeg = dfs(i)\n",
    "                #print(f'\\nstart {i=} {cnt=} {vdeg=}')\n",
    "                if cnt * (cnt-1) == vdeg:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        visited = [False for _ in range(n)]\n",
    "        connection = collections.defaultdict(list)\n",
    "        for edge in edges:\n",
    "            connection[edge[0]].append(edge[1])\n",
    "            connection[edge[1]].append(edge[0])\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                visited[i] = True\n",
    "                cur = [i]\n",
    "                q = collections.deque()\n",
    "                q.append(i)\n",
    "                while q:\n",
    "                    tmp = q.popleft()\n",
    "                    for j in connection[tmp]:\n",
    "                        if not visited[j]:\n",
    "                            visited[j] = True\n",
    "                            cur.append(j)\n",
    "                            q.append(j)\n",
    "                for j in cur:\n",
    "                    if not len(cur) == len(connection[j]) + 1:\n",
    "                        break\n",
    "                else:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        parent = {i : i for i in range(n)}\n",
    "        def find(node):\n",
    "            path = []\n",
    "            while node != parent[node]:\n",
    "                path.append(node)\n",
    "                node = parent[node]\n",
    "            for p in path:\n",
    "                parent[p] = node \n",
    "            return node \n",
    "        \n",
    "        def union(n1, n2):\n",
    "            p1 = find(n1)\n",
    "            p2 = find(n2)\n",
    "            if p1 != p2:\n",
    "                parent[p1] = p2 \n",
    "        \n",
    "        ind = collections.Counter()\n",
    "        for a, b in edges:\n",
    "            union(a, b)\n",
    "            ind[a] += 1 \n",
    "            ind[b] += 1\n",
    "        res = 0\n",
    "        dic = collections.defaultdict(list)\n",
    "        for node in range(n):\n",
    "            dic[find(node)].append(node)\n",
    "        for node in range(n):\n",
    "            if find(node) == node:\n",
    "                for nei in dic[node]:\n",
    "                    if ind[nei] != len(dic[node]) - 1:\n",
    "                        break \n",
    "                else:\n",
    "                    res += 1 \n",
    "        return res  \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        \n",
    "        for edge in edges:\n",
    "            g[edge[0]].append(edge[1])\n",
    "            g[edge[1]].append(edge[0])\n",
    "\n",
    "        vis = [False] * n\n",
    "        def dfs(u: int) -> None:\n",
    "            nonlocal e,v\n",
    "            vis[u] = True\n",
    "            v += 1\n",
    "            for x in g[u]:\n",
    "                e += 1\n",
    "                if not vis[x]:\n",
    "                    dfs(x)\n",
    "        ans = 0\n",
    "        for i, x in enumerate(vis):\n",
    "            if not x:\n",
    "                v = 0\n",
    "                e = 0\n",
    "                dfs(i)\n",
    "                ans += (e == v * (v - 1))\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        es = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            es[i].append(j)\n",
    "            es[j].append(i)\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal v, e\n",
    "            vis.add(node)\n",
    "            e += len(es[node])\n",
    "            v += 1\n",
    "            for j in es[node]:\n",
    "                if j not in vis:\n",
    "                    dfs(j)\n",
    "\n",
    "        vis = set()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i not in vis:\n",
    "                v = e = 0\n",
    "                dfs(i)\n",
    "                ans += e == v*(v-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.parents = list(range(n))\n",
    "        \n",
    "    def find(self, num):\n",
    "        if num != self.parents[num]:\n",
    "            self.parents[num] = self.find(self.parents[num])\n",
    "        return self.parents[num]\n",
    "    \n",
    "    def union(self, num1, num2):\n",
    "        parent1, parent2 = self.find(num1), self.find(num2)\n",
    "        if parent1 == parent2:\n",
    "            return\n",
    "        \n",
    "        if parent1 <= parent2:\n",
    "            self.parents[parent2] = parent1\n",
    "        else:\n",
    "            self.parents[parent1] = parent2\n",
    "            \n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        in_degrees = [0] * n\n",
    "        for f, t in edges:\n",
    "            uf.union(f, t)\n",
    "            in_degrees[f] += 1\n",
    "            in_degrees[t] += 1\n",
    "            \n",
    "        parent_nodes_dict = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            parent_nodes_dict[uf.find(i)].append(i)\n",
    "            \n",
    "        ans = 0\n",
    "        for nodes in parent_nodes_dict.values():\n",
    "            cnt = len(nodes)\n",
    "            if cnt < 2:\n",
    "                ans += 1\n",
    "            else:\n",
    "                is_satisfied = True\n",
    "                for nd in nodes:\n",
    "                    if in_degrees[nd] != cnt - 1:\n",
    "                        is_satisfied = False\n",
    "                ans += is_satisfied\n",
    "        return ans\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges: \n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        vis = [False] * n\n",
    "        def dfs(x: int) -> None:\n",
    "            vis[x] = True\n",
    "            nonlocal e, v\n",
    "            v += 1\n",
    "            e += len(g[x])\n",
    "            \n",
    "            for y in g[x]:\n",
    "                if not vis[y]:\n",
    "                    dfs(y)\n",
    "        \n",
    "        ans = 0\n",
    "        for i, t in enumerate(vis):\n",
    "            if not t:\n",
    "                e, v = 0, 0\n",
    "                dfs(i)\n",
    "                ans += e == v * (v - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        uf = UnionFind(n) # 初始化size为n的并查集\n",
    "\n",
    "        # graph = [[] for _ in range(n)] \n",
    "        for edge in edges:\n",
    "            # a, b = edge[0], edge[1]\n",
    "            # graph[a].append(b) \n",
    "            # graph[b].append(a) \n",
    "            uf.merge(edge[0], edge[1])\n",
    "\n",
    "        res = 0\n",
    "        visited = set()\n",
    "        # 所有的component\n",
    "        for r in uf.parent:\n",
    "            if uf.find(r) == r and r not in visited:\n",
    "                visited.add(r) # 根节点\n",
    "                m = uf.size[r]\n",
    "                if m * (m-1) >> 1 == uf.edge[r]:\n",
    "                    res += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1]*n\n",
    "        self.edge = [0]*n\n",
    "    def find(self, x) -> int:\n",
    "        parent = self.parent\n",
    "        if parent[x] == x:\n",
    "            return x\n",
    "        parent[x] = self.find(parent[x]) # 路径压缩\n",
    "        return parent[x]\n",
    "    def merge(self, x, y):\n",
    "        # \n",
    "        size, parent, edge = self.size, self.parent, self.edge\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if x == y:\n",
    "            edge[x] += 1\n",
    "            return 0\n",
    "        else:\n",
    "            if size[x] < size[y]:\n",
    "                parent[x] = y\n",
    "                size[y] += size[x]\n",
    "                edge[y] += (edge[x] + 1)\n",
    "            else:\n",
    "                parent[y] = x \n",
    "                size[x] += size[y]\n",
    "                edge[x] += (edge[y] + 1)\n",
    "            return 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,n):\n",
    "        self.parent=list(range(n))\n",
    "        self.cot = n\n",
    "        self.size = [1]*n\n",
    "        self.e_size = [0]*n\n",
    "\n",
    "    def find(self, x):\n",
    "        while not x==self.parent[x]:\n",
    "            self.parent[x] = self.parent[self.parent[x]]\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX==rootY:\n",
    "            self.e_size[rootY] += 1\n",
    "            return\n",
    "        if self.size[rootX] > self.size[rootY]:\n",
    "            rootX, rootY = rootY, rootX\n",
    "        self.size[rootY] += self.size[rootX]\n",
    "        self.e_size[rootY] += (self.e_size[rootX] + 1)\n",
    "        self.parent[rootX] = rootY\n",
    "        self.cot -=1\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        for u,v in edges:\n",
    "            uf.union(u, v)\n",
    "        root_list = set()\n",
    "        for i in range(n):\n",
    "            root_list.add(uf.find(i))\n",
    "        res = 0\n",
    "        for r in root_list:\n",
    "            size = uf.size[r]\n",
    "            if uf.e_size[r] == (size*size-size)//2:\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        vis=[False]*n\n",
    "        def dfs(x):\n",
    "            vis[x]=True\n",
    "            nonlocal v,e\n",
    "            v+=1\n",
    "            e+=len(g[x])\n",
    "            for y in g[x]:\n",
    "                if not vis[y]:\n",
    "                    dfs(y)\n",
    "        ans=0\n",
    "        for i,b in enumerate(vis):\n",
    "            if not b:\n",
    "                v=e=0\n",
    "                dfs(i)\n",
    "                ans+=e==v*(v-1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        ans = 0\n",
    "        vis = set()\n",
    "        for i in range(n):\n",
    "            if i in vis: continue\n",
    "            cnt = set()\n",
    "            def dfs(curr, fa):\n",
    "                if curr in cnt:\n",
    "                    return\n",
    "                cnt.add(curr)\n",
    "                vis.add(curr)\n",
    "                for v in g[curr]:\n",
    "                    if v != fa:\n",
    "                        dfs(v, curr)\n",
    "            dfs(i, -1)\n",
    "            yes = True\n",
    "            for x in cnt:\n",
    "                if len(g[x]) != len(cnt) - 1:\n",
    "                    yes = False\n",
    "                    break\n",
    "                for j in g[x]:\n",
    "                    if j not in cnt:\n",
    "                        yes = False\n",
    "                        break\n",
    "                if not yes:\n",
    "                    break\n",
    "            if yes:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        p = list(range(n))\n",
    "        cnt = [0] * n\n",
    "        \n",
    "        def find(x):\n",
    "            while x != p[x]: p[x] = x = p[p[x]]\n",
    "            return x\n",
    "        \n",
    "        for e in edges:\n",
    "            a, b = map(find, e)\n",
    "            if a != b:\n",
    "                p[find(a)] = find(b)\n",
    "                cnt[b] += cnt[a]\n",
    "            cnt[b] += 1\n",
    "\n",
    "        return sum(cnt[x] == v * (v - 1) // 2 for x, v in Counter(map(find, p)).items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        visited=[False]*n\n",
    "        def dfs(x):\n",
    "            visited[x]=True\n",
    "            nonlocal v,e\n",
    "            v+=1\n",
    "            e+=len(g[x])\n",
    "            for y in g[x]:\n",
    "                if not visited[y]:\n",
    "                    dfs(y)\n",
    "        \n",
    "        ans=0\n",
    "        for i,b in enumerate(visited):\n",
    "            if not b:\n",
    "                v=e=0\n",
    "                dfs(i)\n",
    "                ans+=e==v*(v-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        visit = [False]*n\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        def dfs(x: int) ->  None:\n",
    "            visit[x] = True\n",
    "            nonlocal v, e\n",
    "            v += 1\n",
    "            e += len(g[x])\n",
    "            for y in g[x]:\n",
    "                if not visit[y]:\n",
    "                    dfs(y)\n",
    "        ans = 0 \n",
    "        for i,b in enumerate(visit):\n",
    "            if not b:\n",
    "                v = e = 0\n",
    "                dfs(i)\n",
    "                ans += (e==v*(v-1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        if not edges:\n",
    "            return n\n",
    "\n",
    "        idx = list(range(n))\n",
    "        def find_idx(x):\n",
    "            if idx[x] != x:\n",
    "                idx[x] = find_idx(idx[x])\n",
    "            return idx[x]\n",
    "\n",
    "        edges = sorted(edges, key=lambda x:x[0])\n",
    "        ans = defaultdict(int)\n",
    "        for a, b in edges:\n",
    "            a_x = find_idx(a)\n",
    "            b_x = find_idx(b)\n",
    "            if a_x != b_x:\n",
    "                if a_x > b_x:\n",
    "                    idx[a_x] = b_x\n",
    "                else:\n",
    "                    idx[b_x] = a_x\n",
    "        for a, b in edges:\n",
    "            a_x = find_idx(a)\n",
    "            b_x = find_idx(b)\n",
    "            if a_x == b_x:\n",
    "                ans[a_x] += 1\n",
    " \n",
    "        res = Counter(idx)\n",
    "        result = 0\n",
    "        for key, value in res.items():\n",
    "            if value*(value-1)/2 == ans[key] :\n",
    "                result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        ans = 0\n",
    "        visited = [False] * n\n",
    "\n",
    "        def dfs(x):\n",
    "            visited[x] = True\n",
    "            nonlocal e, v\n",
    "            v += 1\n",
    "            e += len(g[x])\n",
    "            for y in g[x]:\n",
    "                if not visited[y]:\n",
    "                    dfs(y)\n",
    "\n",
    "\n",
    "        for i, been in enumerate(visited):\n",
    "            if not been:\n",
    "                e, v = 0, 0\n",
    "                dfs(i) #\n",
    "                ans += e == v * (v - 1)\n",
    "\n",
    "        return ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        s = [x for x in range(n)]\n",
    "        cnt = [0] * n\n",
    "        def find(x: int) -> int:\n",
    "            if x != s[x]:\n",
    "                s[x] = find(s[x])\n",
    "            return s[x]\n",
    "        def merge(x: int, y: int) -> int:\n",
    "            rootx = find(x)\n",
    "            rooty = find(y)\n",
    "            if rootx != rooty:\n",
    "                s[rootx] = rooty\n",
    "        for x,y in edges:\n",
    "            cnt[x] +=1\n",
    "            cnt[y] +=1\n",
    "            merge(x, y)\n",
    "        group = defaultdict(list)\n",
    "        ans = 0\n",
    "        for x in range(n):\n",
    "            group[find(x)].append(x)\n",
    "        for nums in group.values():\n",
    "            n = len(nums)\n",
    "            if all(cnt[x] == n - 1 for x in nums):\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        uf = UnionFind(n)\n",
    "\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            a, b = edge[0], edge[1]\n",
    "            graph[a].append(b) \n",
    "            graph[b].append(a) \n",
    "            uf.merge(a, b)\n",
    "\n",
    "        res = 0\n",
    "        visited = set()\n",
    "        # 所有的component\n",
    "        for r in uf.parent:\n",
    "            if uf.find(r) == r and r not in visited:\n",
    "                # 根节点\n",
    "                visited.add(r)\n",
    "                # print(uf.edge[r])\n",
    "                m = uf.size[r]\n",
    "                if m * (m-1) >> 1 == uf.edge[r]:\n",
    "                    res += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1]*n\n",
    "        self.edge = [0]*n\n",
    "    def find(self, x) -> int:\n",
    "        parent = self.parent\n",
    "        if parent[x] == x:\n",
    "            return x\n",
    "        parent[x] = self.find(parent[x]) # 路径压缩\n",
    "        return parent[x]\n",
    "    def merge(self, x, y):\n",
    "        # \n",
    "        size, parent, edge = self.size, self.parent, self.edge\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if x == y:\n",
    "            edge[x] += 1\n",
    "            return 0\n",
    "        else:\n",
    "            if size[x] < size[y]:\n",
    "                parent[x] = y\n",
    "                size[y] += size[x]\n",
    "                edge[y] += (edge[x] + 1)\n",
    "            else:\n",
    "                parent[y] = x \n",
    "                size[x] += size[y]\n",
    "                edge[x] += (edge[y] + 1)\n",
    "            return 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        1.判连通 并查集\n",
    "        2.有没有边 map\n",
    "        \"\"\"\n",
    "        def find(x:int) ->int :\n",
    "            if x!=s[x] :\n",
    "                s[x]=find(s[x])\n",
    "            return s[x]\n",
    "        def merge(x:int, y:int) :\n",
    "            rootx=find(x)\n",
    "            rooty=find(y)\n",
    "            if rootx!=rooty :\n",
    "                s[rootx]=rooty\n",
    "        s=[0]*n\n",
    "        for i in range(1,n) :\n",
    "            s[i]=i\n",
    "        deg=[0]*n\n",
    "        for a,b in edges :\n",
    "            deg[a]+=1\n",
    "            deg[b]+=1\n",
    "            merge(a,b)\n",
    "        group=defaultdict(list)\n",
    "        for x in range(n) :\n",
    "            group[find(x)].append(x)\n",
    "        ans=0\n",
    "        for g in group.values() :\n",
    "            l=len(g)\n",
    "            if all(deg[x]==l-1 for x in g ) :\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        vis = [False] * n\n",
    "        def dfs(x: int) -> None:\n",
    "            vis[x] = True\n",
    "            nonlocal v, e\n",
    "            v += 1\n",
    "            e += len(g[x])\n",
    "            for y in g[x]:\n",
    "                if not vis[y]:\n",
    "                    dfs(y)\n",
    "\n",
    "        ans = 0\n",
    "        for i, b in enumerate(vis):\n",
    "            if not b:\n",
    "                v = e = 0\n",
    "                dfs(i)\n",
    "                ans += e == v * (v - 1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, x: int, g: List[List[int]], vis: List[bool], counts: List[int]) -> None:\n",
    "        vis[x] = True\n",
    "        counts[0] += 1\n",
    "        counts[1] += len(g[x])\n",
    "        for y in g[x]:\n",
    "            if not vis[y]:\n",
    "                self.dfs(y, g, vis, counts)\n",
    "\n",
    "    def countCompleteComponents(self,n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        vis = [False] * n\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                counts = [0, 0]  # Use a list to hold v and e\n",
    "                self.dfs(i, g, vis, counts)\n",
    "                v, e = counts\n",
    "                ans += e == v * (v - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self,N):\n",
    "        self.parent = [i for i in range(N)]\n",
    "    def find(self,x):\n",
    "        st = x\n",
    "        while self.parent[x] != x:\n",
    "            x = self.parent[x]\n",
    "        self.parent[st] = x\n",
    "        return x \n",
    "    def union(self,x,y):\n",
    "        self.parent[self.find(x)] = self.parent[self.find(y)]\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 感觉可以用并查集来解决\n",
    "        dsu = DSU(n)\n",
    "        innode = [0]*n \n",
    "        for st,end in edges:\n",
    "            dsu.union(st,end)\n",
    "            innode[st] += 1\n",
    "            innode[end] += 1 \n",
    "\n",
    "        hashmap = {}\n",
    "        for i in range(len(dsu.parent)):\n",
    "            if dsu.parent[dsu.find(i)] in hashmap:\n",
    "                hashmap[dsu.parent[dsu.find(i)]].append(i)\n",
    "            else:\n",
    "                hashmap[dsu.parent[dsu.find(i)]] = [i] \n",
    "        # print(hashmap)\n",
    "        # 没有仔细读题,要求是每对节点之间都存在边\n",
    "        res = 0 \n",
    "        for i in hashmap.keys():\n",
    "            Flag = True \n",
    "            for node in hashmap[i]:\n",
    "                if innode[node] != len(hashmap[i])-1:\n",
    "                    Flag = False\n",
    "                    break \n",
    "            if Flag:\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        ans = 0\n",
    "        vis = [False] * n\n",
    "        def dfs(x):\n",
    "            vis[x] = True\n",
    "            nonlocal v, e\n",
    "            v += 1\n",
    "            e += len(g[x])\n",
    "            for y in g[x]:\n",
    "                if not vis[y]:\n",
    "                    dfs(y)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                v = e = 0\n",
    "                dfs(i)\n",
    "                ans += e == v * (v - 1)\n",
    "\n",
    "        return ans\n",
    "\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        nb = defaultdict(list)\n",
    "        deg = [0] * n\n",
    "        for a, b in edges:\n",
    "            deg[a] += 1\n",
    "            deg[b] += 1\n",
    "            nb[a].append(b)\n",
    "            nb[b].append(a)\n",
    "\n",
    "        vis = [0] * n\n",
    "        def dfs(node):\n",
    "            nonlocal cnt, pathcnt\n",
    "            vis[node] =1\n",
    "            for ch in nb[node]:\n",
    "                if not vis[ch]:\n",
    "                    cnt += 1\n",
    "                    pathcnt += deg[ch]\n",
    "                    dfs(ch)\n",
    "        res = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                cnt, pathcnt = 1,deg[i]\n",
    "                dfs(i)\n",
    "                \n",
    "                if cnt * (cnt-1) == pathcnt:\n",
    "                    res += 1 \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 初始化邻接表\n",
    "        graph = {i: [] for i in range(n)}\n",
    "\n",
    "        # 构建邻接表\n",
    "        for edge in edges:\n",
    "            u, v = edge\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "\n",
    "        def dfs(graph, start, visited):\n",
    "            visited.add(start)\n",
    "            count = 1  # 初始化节点数量为1\n",
    "            edge_count = 0  # 初始化边的个数为0\n",
    "            for neighbor in graph[start]:\n",
    "                if neighbor not in visited:\n",
    "                    count_neighbor, count_edge = dfs(graph, neighbor, visited)\n",
    "                    count += count_neighbor\n",
    "                    edge_count += count_edge\n",
    "            edge_count += len(graph[start])  # 统计当前节点的边的个数\n",
    "            return count, edge_count\n",
    "\n",
    "        def count_connected_components(graph):\n",
    "            visited = set()\n",
    "            components = []  # 存储各连通分量的节点数量和边的数量\n",
    "            for node in graph:\n",
    "                if node not in visited:\n",
    "                    component_size, edge_count = dfs(graph, node, visited)\n",
    "                    components.append((component_size, edge_count // 2))\n",
    "            return len(components), components\n",
    "\n",
    "        res = 0\n",
    "        n, components = count_connected_components(graph)\n",
    "        for component in components:\n",
    "            # print(f\"component = {component}\")\n",
    "            nodes = component[0]\n",
    "            edges = component[1]\n",
    "            if nodes * (nodes - 1) // 2 == edges:\n",
    "                res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        dct=[[]for i in range(n)]\n",
    "        ans=0\n",
    "        fa=[i for i in range(n)]\n",
    "        def find(x):\n",
    "            if fa[x]!=x:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(a,b):\n",
    "            x,y=find(a),find(b)\n",
    "            if x!=y:\n",
    "                fa[y]=x\n",
    "            \n",
    "        for a,b in edges:\n",
    "            dct[a].append(b)\n",
    "            dct[b].append(a)\n",
    "            union(a,b)\n",
    "        s=set()\n",
    "        for i in range(n):\n",
    "            if i not in s:\n",
    "                ss=set()\n",
    "                for j in range(n):\n",
    "                    if find(j)==find(i):\n",
    "                        s.add(j)\n",
    "                        ss.add(j)\n",
    "                c=True\n",
    "                for x in ss:\n",
    "                    for y in ss:\n",
    "                        if x!=y:\n",
    "                            if y not in dct[x] or x not in dct[y]:\n",
    "                                c=False\n",
    "                                break\n",
    "                    if not c:\n",
    "                        break\n",
    "                if c:\n",
    "                    ans+=1\n",
    "        return ans\n",
    "\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        vis=[False]*n\n",
    "        def dfs(x):\n",
    "            vis[x]=True\n",
    "            nonlocal v,e\n",
    "            v+=1\n",
    "            e+=len(g[x])\n",
    "            for y in g[x]:\n",
    "                if not vis[y]:\n",
    "                    dfs(y)\n",
    "        ans=0\n",
    "        for i,b in enumerate(vis):\n",
    "            if not b:\n",
    "                v=e=0\n",
    "                dfs(i)\n",
    "                ans+=e==v*(v-1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        vis = [False] * n\n",
    "        def dfs(x: int) -> None:\n",
    "            vis[x] = True\n",
    "            nonlocal v, e\n",
    "            v += 1\n",
    "            e += len(g[x])\n",
    "            for y in g[x]:\n",
    "                if not vis[y]:\n",
    "                    dfs(y)\n",
    "\n",
    "        ans = 0\n",
    "        for i, b in enumerate(vis):\n",
    "            if not b:\n",
    "                v = e = 0\n",
    "                dfs(i)\n",
    "                ans += e == v * (v - 1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        parent = list(range(n))\n",
    "        size = [1] * n\n",
    "        def find(x):\n",
    "            if x != parent[x]:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        def uinon(x, y):\n",
    "            if find(x) == find(y):\n",
    "                return\n",
    "            rx, ry = find(x), find(y)\n",
    "            if size[rx] < size[ry]:\n",
    "                rx, ry = ry, rx\n",
    "            size[rx] += size[ry]\n",
    "            parent[ry] = rx\n",
    "        ga = defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            uinon(a, b)\n",
    "            ga[a].add(b)\n",
    "            ga[b].add(a)  \n",
    "        g = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            pa = find(i)\n",
    "            g[pa].append(i)\n",
    "        ans = 0\n",
    "        for k, v in g.items():    \n",
    "            if len(v) == 1:\n",
    "                ans += 1\n",
    "            else:\n",
    "                flag = True\n",
    "                for x in v:\n",
    "                    for y in v:\n",
    "                        if x != y:\n",
    "                            if y not in ga[x]:\n",
    "                                flag = False\n",
    "                if flag:\n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        \n",
    "        visited = [False] * n\n",
    "        def dfs(x: int) -> None:\n",
    "            visited[x] = True\n",
    "            nonlocal v, e\n",
    "            v += 1\n",
    "            e += len(graph[x])\n",
    "            for y in graph[x]:\n",
    "                if not visited[y]:\n",
    "                    dfs(y)\n",
    "        \n",
    "        ans = 0\n",
    "        for i, s in enumerate(visited):\n",
    "            if not s:\n",
    "                v = e = 0\n",
    "                dfs(i)\n",
    "                ans += e == v * (v - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        t = defaultdict(lambda: [False]*n)\n",
    "        for e in edges:\n",
    "            t[e[0]][e[1]] = True\n",
    "            t[e[1]][e[0]] = True\n",
    "        ans = n - len(t)\n",
    "        t_set = [False] * n\n",
    "        for e in edges:\n",
    "            if not t_set[e[0]]:\n",
    "                cur = [e[0], e[1]]\n",
    "                com = [e[0], e[1]]\n",
    "                t_set[e[0]] = True\n",
    "                t_set[e[1]] = True\n",
    "                while len(cur) > 0:\n",
    "                    tmp = cur\n",
    "                    cur = []\n",
    "                    for tp in tmp:\n",
    "                        for j, x in enumerate(t[tp]):\n",
    "                            if x and not t_set[j]:\n",
    "                                t_set[j] = True\n",
    "                                cur.append(j)\n",
    "                                com.append(j)\n",
    "                isValid = 1\n",
    "                for i, c1 in enumerate(com):\n",
    "                    for c2 in com[i+1:]:\n",
    "                        if not t[c1][c2]:\n",
    "                            isValid = 0\n",
    "                            break\n",
    "                    if not isValid:\n",
    "                        break\n",
    "                ans += isValid\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 初始化邻接表\n",
    "        graph = {i: [] for i in range(n)}\n",
    "\n",
    "        # 构建邻接表\n",
    "        for edge in edges:\n",
    "            u, v = edge\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "\n",
    "        def dfs(graph, start, visited):\n",
    "            visited.add(start)\n",
    "            count = 1  # 初始化节点数量为1\n",
    "            edge_count = 0  # 初始化边的个数为0\n",
    "            for neighbor in graph[start]:\n",
    "                if neighbor not in visited:\n",
    "                    count_neighbor, count_edge = dfs(graph, neighbor, visited)\n",
    "                    count += count_neighbor\n",
    "                    edge_count += count_edge\n",
    "            edge_count += len(graph[start])  # 统计当前节点的边的个数\n",
    "            return count, edge_count\n",
    "\n",
    "        def count_connected_components(graph):\n",
    "            visited = set()\n",
    "            components = []  # 存储各连通分量的节点数量和边的数量\n",
    "            for node in graph:\n",
    "                if node not in visited:\n",
    "                    component_size, edge_count = dfs(graph, node, visited)\n",
    "                    components.append((component_size, edge_count // 2))\n",
    "            return len(components), components\n",
    "\n",
    "        res = 0\n",
    "        n, components = count_connected_components(graph)\n",
    "        for component in components:\n",
    "            print(f\"component = {component}\")\n",
    "            nodes = component[0]\n",
    "            edges = component[1]\n",
    "            if nodes * (nodes - 1) // 2 == edges:\n",
    "                res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        parent = list(range(n))\n",
    "        rankp = [1]*n ## 点数\n",
    "        ranke =[0]*n  ## 边数\n",
    "\n",
    "\n",
    "        def find(x:int)->int:\n",
    "            if x!=parent[x]:\n",
    "                parent[x] = find(parent[x]) \n",
    "            return parent[x]\n",
    "\n",
    "        def merge(x:int,y:int)->None:\n",
    "            px,py = find(x),find(y)\n",
    "            if px !=py:\n",
    "                parent[px] =py\n",
    "                rankp[py]+=rankp[px]\n",
    "                ranke[py] += ranke[px]\n",
    "        \n",
    "        for x,y in edges:\n",
    "            merge(x,y)\n",
    "            ranke[find(x)]+=1\n",
    "\n",
    "        ans = 0 \n",
    "        for i in range(n):\n",
    "            if i == parent[i] and ranke[i] == (rankp[i] * (rankp[i]-1))//2:\n",
    "                ans+=1\n",
    "\n",
    "        return ans\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        vis = [False] * n\n",
    "        def dfs(x: int) -> None:\n",
    "            vis[x] = True\n",
    "            nonlocal v, e\n",
    "            v += 1\n",
    "            e += len(g[x])\n",
    "            for y in g[x]:\n",
    "                if not vis[y]:\n",
    "                    dfs(y)\n",
    "\n",
    "        ans = 0\n",
    "        for i, b in enumerate(vis):\n",
    "            if not b:\n",
    "                v = e = 0\n",
    "                dfs(i)\n",
    "                ans += e == v * (v - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "      g = [[] for _ in range(n)]\n",
    "      vis = [False] * n\n",
    "      ans = 0\n",
    "      for x, y in edges:\n",
    "        g[x].append(y)\n",
    "        g[y].append(x)\n",
    "      def dfs(x):\n",
    "        nonlocal e, v\n",
    "        v += 1\n",
    "        e += len(g[x])\n",
    "        vis[x] = True\n",
    "        for y in g[x]:\n",
    "          if not vis[y]:\n",
    "            dfs(y)\n",
    "      for i, b in enumerate(vis):\n",
    "        e = v = 0\n",
    "        if not b:\n",
    "          dfs(i)\n",
    "          ans += e == v * (v - 1)\n",
    "      return ans\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        vis = [False] * n\n",
    "        d = [0] * n\n",
    "        res = 0\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "            d[x] += 1\n",
    "            d[y] += 1\n",
    "        \n",
    "        def dfs(x):\n",
    "            nonlocal v, e\n",
    "            vis[x] = True\n",
    "            e += d[x]\n",
    "            v += 1\n",
    "            for y in g[x]:\n",
    "                if not vis[y]:\n",
    "                    dfs(y)\n",
    "            \n",
    "\n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                v, e = 0, 0\n",
    "                dfs(i)\n",
    "                print(v, e)\n",
    "                res += (e == v * (v - 1))\n",
    "        return res\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        e = collections.defaultdict(list)\n",
    "        p = list(range(n))\n",
    "        cnt = [1] * n\n",
    "        total = [0] * n\n",
    "        for x, y in edges:\n",
    "            e[x].append(y)\n",
    "            e[y].append(x)\n",
    "        seen = set()\n",
    "        def dfs(node):\n",
    "            seen.add(node)\n",
    "            cnt = 1\n",
    "            total = 0\n",
    "            for ne in e[node]:\n",
    "                total += 1\n",
    "                if ne not in seen:\n",
    "                    x, y = dfs(ne)\n",
    "                    total += y\n",
    "                    cnt += x\n",
    "            return cnt, total\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if i not in seen:\n",
    "                x, y = dfs(i)\n",
    "                # print(i, x, y)\n",
    "                if y == x * (x - 1):\n",
    "                    res += 1\n",
    "            \n",
    "        return res\n",
    "                \n",
    "        \n",
    "                    \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        vis = [False] * n\n",
    "        res = 0\n",
    "        dfd = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            dfd[a].append(b)\n",
    "            dfd[b].append(a)\n",
    "        def dfs(u):\n",
    "            vis[u] = True\n",
    "            nonlocal v, e\n",
    "            v += 1\n",
    "            e += len(dfd[u])\n",
    "            for ne in dfd[u]:\n",
    "                if not vis[ne]: dfs(ne)\n",
    "\n",
    "        for i in range(n):\n",
    "            if len(dfd[i]) == 0: res += 1\n",
    "            elif not vis[i]:\n",
    "                v, e = 0, 0\n",
    "                dfs(i)\n",
    "                if v * (v - 1) == e: res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class AndSet:\n",
    "    def __init__(self, n):\n",
    "        # self.num = n\n",
    "        self.father = [i for i in range(n)]\n",
    "\n",
    "    def find(self, u):\n",
    "        if u == self.father[u]:\n",
    "            return u\n",
    "        else:\n",
    "            self.father[u] = self.find(self.father[u])  # 路径压缩\n",
    "            return self.father[u]\n",
    "\n",
    "    def join(self, f, c):\n",
    "        f = self.find(f)\n",
    "        c = self.find(c)\n",
    "        if f == c:\n",
    "            return\n",
    "        else:\n",
    "            self.father[c] = f\n",
    "\n",
    "    def same(self, u, v):\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        return u == v\n",
    "\n",
    "    # def getRoot(self, u):\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        andSet = AndSet(n=n)\n",
    "        count = 0\n",
    "        for edge in edges:\n",
    "            if not andSet.same(edge[0], edge[1]):\n",
    "                andSet.join(edge[0], edge[1])\n",
    "        d = {}\n",
    "        for i in range(n):\n",
    "            try:\n",
    "                d[andSet.find(i)].append(i)\n",
    "            except KeyError:\n",
    "                d[andSet.find(i)] = [i]\n",
    "        for val in d.values():\n",
    "            comb = list(itertools.combinations(val, 2))\n",
    "            if comb:\n",
    "                for c in comb:\n",
    "                    if [c[0], c[1]] in edges or [c[1], c[0]] in edges:\n",
    "                        continue\n",
    "                    else:\n",
    "                        break\n",
    "                else:\n",
    "                    count += 1\n",
    "            else:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        visited = [0]*n\n",
    "        ans = 0\n",
    "        def dfs(x):\n",
    "            nonlocal v,e\n",
    "            visited[x] = 1\n",
    "            e += len(g[x])\n",
    "            v += 1\n",
    "            for y in g[x]:\n",
    "                if not visited[y]:\n",
    "                    dfs(y)\n",
    "        #在完全图中，任意两点之间都有边，相当于从 v点中选 2 个点的方案数,边数 = v*(v-1)\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                v = e = 0 #分别统计点数和边数\n",
    "                dfs(i)\n",
    "                if v*(v-1) == e:\n",
    "                    ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # parent = list(range(n))\n",
    "        # def find(x):\n",
    "        #     if parent[x] != x:\n",
    "        #         parent[x] = find(parent[x])\n",
    "        #     return parent[x]\n",
    "        # for i,j in edges:\n",
    "        #     a,b = find(i),find(j)\n",
    "        #     if a != b:\n",
    "        #         parent[a] = b\n",
    "        # cnt = 0\n",
    "        # for i in range(n):\n",
    "        #     if parent[i] == i:\n",
    "        #         cnt += 1\n",
    "        # print(parent)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        visited = [0]*n\n",
    "        ans = 0\n",
    "        def dfs(x):\n",
    "            v = e = 0\n",
    "            visited[x] = 1\n",
    "            v += 1\n",
    "            e += len(g[x])\n",
    "            for y in g[x]:\n",
    "                if not visited[y]:\n",
    "                    a,b = dfs(y)\n",
    "                    v += a\n",
    "                    e += b \n",
    "            return v,e\n",
    "        #在完全图中，任意两点之间都有边，相当于从 v点中选 2 个点的方案数,边数 = v*(v-1)\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                # v = e = 0 #分别统计点数和边数\n",
    "                v , e = dfs(i)\n",
    "                if v*(v-1) == e:\n",
    "                    ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # parent = list(range(n))\n",
    "        # def find(x):\n",
    "        #     if parent[x] != x:\n",
    "        #         parent[x] = find(parent[x])\n",
    "        #     return parent[x]\n",
    "        # for i,j in edges:\n",
    "        #     a,b = find(i),find(j)\n",
    "        #     if a != b:\n",
    "        #         parent[a] = b\n",
    "        # cnt = 0\n",
    "        # for i in range(n):\n",
    "        #     if parent[i] == i:\n",
    "        #         cnt += 1\n",
    "        # print(parent)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:\n",
    "        def dfs(i: int) -> Tuple[int, int]:\n",
    "            \"\"\"遍历当前节点所在的连通分量，返回连通分量的节点数和边数\"\"\"\n",
    "            if visited[i]:\n",
    "                return 0, 0\n",
    "            visited[i] = True\n",
    "            V, E = 1, 0 \n",
    "\n",
    "            # 遍历其他n-1个节点\n",
    "            for j in range(n):  # O(N)\n",
    "                if j != i and isConnected[i][j]:\n",
    "                    v, e = dfs(j)\n",
    "                    V += v  \n",
    "                    E += 1 + e \n",
    "            \n",
    "            return V, E\n",
    "\n",
    "        # build adjacency matrix for undirected graph\n",
    "        # 1 is connected, 0 is unconnected\n",
    "        isConnected = [[0]*n for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            isConnected[u-1][v-1] = isConnected[v-1][u-1] = 1\n",
    "\n",
    "        visited = [False] * n \n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):  # O(N)\n",
    "            # 若节点未访问过，说明属于新的连通分量\n",
    "            if not visited[i]:\n",
    "                V, E = dfs(i)\n",
    "                if E == V*(V-1):\n",
    "                    ans += 1\n",
    "\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
